package 二叉树及操作;

public class BinaryTree {
    private BinaryTreeNode root;

    //初始化二叉树
    public BinaryTree(){}

    public BinaryTree(BinaryTreeNode root){
        this.root = root;
    }

    public void setRoot(BinaryTreeNode root){
        this.root = root;
    }

    public BinaryTreeNode getRoot(){
        return root;
    }

    /*二叉树清空操作*/
    public void clear(BinaryTreeNode node){
        if(node!=null){
            clear(node.getLeftNode());
            clear(node.getRightNode());
            node=null;
        }
    }
    /*清空树*/
    public void clearTree(BinaryTreeNode root){
        clear(root);
    }

    /*判断节点是否为空*/
    public boolean isEmpty(){
        return root==null;
    }

    /*获取二叉树的高度*/
    public int getTreeHeight(){
        return getHeight(this.root);
    }
    /*获取某一结点的高度*/
    public int getHeight(BinaryTreeNode node){
        if(node==null) {
            return 0;
        }else{
            //递归获取左子树高度
            int l=getHeight(node.getLeftNode());
            //递归获取右子树高度
            int r=getHeight(node.getRightNode());
            return l>r?(l+1):(r+1);
        }
    }

    /*求二叉树的节点数*/
    public int size(){
        return getSize1(root);
    }
    /*递归获取某一结点的节点数*/
    public int getSize1(BinaryTreeNode node) {
        if(node==null){
            return 0;
        }else {
            //计算本节点所以要加1
            return 1+getSize1(node.getLeftNode())+getSize1(node.getLeftNode());
        }
    }
    /*迭代获取某一结点的节点数*/
   /* public int getSize2(BinaryTreeNode node){
        if (node==null){
            return 0;
        }
        int size=0;
        while (node !=null){

        }
    }*/

   /*返回某节点的父节点*/
    public BinaryTreeNode getParent(BinaryTreeNode subTree,BinaryTreeNode node){
        if(subTree==null){
            return null;
        }
        if(subTree.getLeftNode()==node || subTree.getRightNode()==node){
            return subTree;
        }
        BinaryTreeNode parent=null;
        if(getParent(subTree.getLeftNode(),node)!=null){
            parent=getParent(subTree.getLeftNode(),node);
            return parent;
        }else if(getParent(subTree.getRightNode(),node)!=null){
            //递归左右子结点
            return getParent(subTree.getRightNode(),node);
        }else{
            return null;
        }
    }
    //查找node节点在二叉树中的父节点
    public BinaryTreeNode getParent(BinaryTreeNode node){
        return (root==null||root==node)? null:getParent(root,node);
    }

    //获取某个节点的左子树
    public BinaryTreeNode getLeftTree(BinaryTreeNode node){
        return node.getLeftNode();
    }

    //获取某个节点的右子树
    public BinaryTreeNode getRightTree(BinaryTreeNode node){
        return node.getRightNode();
    }

    //给某个节点插入左节点
    public void insertLeft(BinaryTreeNode parent,BinaryTreeNode newnode){
        parent.setLeftNode(newnode);
    }
    //给某个节点插入右节点
    public void insertRitht(BinaryTreeNode parent,BinaryTreeNode newnode){
        parent.setRightNode(newnode);
    }

    //前序遍历
    public void PreOrder(BinaryTreeNode node){
        if(node!=null){
            System.out.println(node.getData()); //先访问根节点
            PreOrder(node.getLeftNode());  //先根遍历左子树
            PreOrder(node.getRightNode());  //先根遍历右子树
        }
    }

    //中序遍历
    public void InOrder(BinaryTreeNode node){
        if(node!=null){
            InOrder(node.getLeftNode());  //中根遍历左子树
            System.out.println(node);    //访问根节点
            InOrder(node.getRightNode());  //中根遍历右子树
        }
    }
    //后跟遍历
    public void PostOrder(BinaryTreeNode node){
        if(node!=null){
            PostOrder(node.getLeftNode());  //后根遍历左子树
            PostOrder(node.getRightNode());  //后根遍历右子树
            System.out.println(node);   //访问根节点
        }
    }

}
